public class SortList {
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode middleNode = findMiddleNode(head);
        ListNode middleNextNode = middleNode.next;
        middleNode.next=null;
        ListNode leftNode = sortList(head);
        ListNode rightNode = sortList(middleNextNode);
        return merge(leftNode, rightNode);
    }

    private ListNode merge(ListNode l1, ListNode l2) {
        ListNode dump=new ListNode(-1);
        ListNode cur=dump;
        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                cur.next=l1;
                l1=l1.next;
            }else{
                cur.next=l2;
                l2=l2.next;
            }
            cur=cur.next;
        }
        cur.next=l1!=null?l1:l2;
        return dump.next;
    }

    private ListNode findMiddleNode(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode slow = head;
        ListNode fast = head.next;

        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;

    }
}
